﻿// 952. 按公因数计算最大组件大小.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <map>
using namespace std;
/*
https://leetcode.cn/problems/largest-component-size-by-common-factor/description/

给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：

有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。
返回 图中最大连通组件的大小 。



示例 1：


输入：nums = [4,6,15,35]
输出：4
示例 2：



输入：nums = [20,50,9,63]
输出：2
示例 3：



输入：nums = [2,3,6,7,4,12,21,39]
输出：8


提示：

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 105
nums 中所有值都 不同
*/



class Solution {
public:
    int f[100010];
    void init() {
        for (int i = 0; i < 100010; i++) f[i] = i;
    }

    int find(int x) {
        if (f[x] != x) f[x] = find(f[x]);
        return f[x];
    }

    void merge(int a, int b) {
        a = find(a); b = find(b);
        f[a] = b;
    }


    int largestComponentSize(vector<int>& nums) {
        init();
        for (int i = 0; i < nums.size(); i++) {
            int val = nums[i];
            for (int j = 2; j <= val / j; j++) {
                while (val % j == 0) {
                    val /= j;
                    merge(nums[i], j);
                }
            }
            if (val != 1) merge(nums[i], val);
        }

        int ans = 0; map<int, int> mm;
        for (int i = 0; i < nums.size(); i++) {
            int top = find(nums[i]);
            mm[top]++;
            ans = max(ans, mm[top]);
        }

        return ans;
    }
};

int main()
{
    std::cout << "Hello World!\n";
}
 